package org.gpf;
/**
 * 斐波那契数列
 * @author gaopengfei
 * @date 2015-5-19 下午4:48:23
 */
public class Fibonacci {

	/**
	 * 递归算法求斐波那契数列0,1,1,2,3,5,8,13……,时间复杂度大约是O(2^n)，空间复杂度为O(n)
	 */
	private static int fib_rev(int number){
		
		return number < 2 ? number : fib_rev(number - 1) + fib_rev(number - 2);
	}
	
	/**
	 * 迭代法求解斐波那契数,时间复杂度为O(n)，只需要3个存储单元,空间复杂度O(1)
	 */
	private static int fib_iter(int number){
		
		int f = 0;				// 保存运算结果
		int f0 = 0,f1 = 1;
		
		if (number == 0)
			return f0;
		else if(number == 1)
			return f1;
		else{
			int start = 2;
			do {
				f = f0 + f1;
				f0 = f1;
				f1 = f;
			} while (start++ < number);
			return f;
		}
	}
	
	/**
	 * 斐波那契数的原始实现
	 * 
	 * @param number
	 * @return
	 */
	private static int fib(int number) {

		int f = 0, g = 1;
		for (int i = 0; i < number; i++) {
			System.out.println(f);
			f = f + g;
			g = f - g;
		}
		return f;

	}

	public static void main(String[] args) {
		
		System.out.println(fib_rev(10));
		System.out.println(fib_iter(10000));
		System.out.println(fib(15));
	}

}
